//import java.lang.reflect.Array;
//import java.util.Arrays;
//
//public class Mystack {
//    private int[] elem;
//    private int usedSize;
//
//    private static final int DEFAULT_CAPACITY = 10;
//
//    public Mystack(){
//        this.elem = new int[DEFAULT_CAPACITY];
//    }
//
//    //放新元素
//    public void push(int val){
//        if (isfull()){
//            elem = Arrays.copyOf(elem, 2*elem.length);
//        }
//        elem[usedSize] = val;
//        usedSize++;
//    }
//
//    //判断数组是否满了
//    public boolean isfull(){
//        if (usedSize >= elem.length){
//            return true;
//        }else{
//            return false;
//        }
//    }
//
//    //露出第一个元素并删除
//    public int pop(){
//        if (isEmpty()){
//            throw new RuntimeException("数组为空");
//        }else {
//            usedSize--;
//            return elem[usedSize];
//        }
//    }
//
//    //露出第一个元素
//    public int peak() {
//        if (isEmpty()) {
//            throw new RuntimeException("数组为空");
//        } else {
//            return elem[usedSize-1];
//        }
//    }
//
//    //判断是否有元素
//    public boolean isEmpty(){
//        return usedSize == 0;
//    }
//}

//有效的括号
//class Solution {
//    public boolean isValid(String s) {
//        int k = 0;
//        Stack<Character> p = new Stack<>();
//        while (k < s.length()) {
//            if (s.charAt(k) == '(' || s.charAt(k) == '[' || s.charAt(k) == '{') {
//                p.push(s.charAt(k));
//                k++;
//            } else {
//                if(p.size() == 0){
//                    return false;
//                }
//                if (s.charAt(k) == ')' && p.peek() == '(' || s.charAt(k) == '}' &&
//                        p.peek() == '{' || s.charAt(k) == ']' && p.peek() == '[') {
//                    p.pop();
//                    k++;
//                } else {
//                    return false;
//                }
//            }
//        }
//        if(p.size() == 0){
//            return true;
//        }else{
//            return false;
//        }
//    }
//}


//逆波兰表达式求值
//class Solution {
//    public int evalRPN(String[] tokens) {
//        int left = 0;
//        int right = 0;
//        int sum = 0;
//        Stack<Integer> s = new Stack<>();
//        for(int j=0; j<tokens.length; j++){
//            if(tokens[j].equals("+") ){
//                right = s.pop();
//                left = s.pop();
//                sum = left+right;
//                s.push(sum);
//            }else if(tokens[j].equals("-")){
//                right = s.pop();
//                left = s.pop();
//                sum = left-right;
//                s.push(sum);
//            }else if(tokens[j].equals("*")){
//                right = s.pop();
//                left = s.pop();
//                sum = left*right;
//                s.push(sum);
//            }else if(tokens[j].equals("/")){
//                right = s.pop();
//                left = s.pop();
//                sum = left/right;
//                s.push(sum);
//            }else{
//                int k = Integer.parseInt(tokens[j]);
//                s.push(k);
//            }
//        }
//        return s.pop();
//    }
//}

//现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode cur = pHead;
        ListNode big = null;
        ListNode bigt = null;
        ListNode small = null;
        ListNode smallt = null;
        while(cur != null){
            if(cur.val < x){
                if(small == null){
                    small = cur;
                    smallt = cur;
                }else{
                    small.next = cur;
                    small = small.next;
                }
            }else{
                if(big == null){
                    big = cur;
                    bigt = cur;
                }else{
                    big.next = cur;
                    big = big.next;
                }
            }
            cur = cur.next;
        }
        if(smallt == null){
            return bigt;
        }else if(bigt == null){
            return smallt;
        }else{
            //链接
            small.next = bigt;
            big.next = null;
            return smallt;
        }
    }
}